package com.lyz.dataStructure.LeetCode;

import com.sun.org.apache.xerces.internal.impl.xs.SchemaNamespaceSupport;

import java.util.Scanner;

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/4/12 11:48
 *@Description:
 **/

/*
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。
 */
public class ArrangeCoins {

        public int arrangeCoins(int n) {
            int low = 0, high = Math.min(n, (1 << 16) - 1), mid = 0, sum = 0;
            while(low <= high){
                mid = (low + high) >> 1;
                sum = ((mid & 1) == 0) ? (mid/2) * (mid + 1) : ((mid + 1)/2) * mid;
                if(sum == n){
                    return mid;
                }else if(sum > n){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
            return sum > n ? mid-1 : mid;
        }


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入数字：");
        while(input.hasNext()){
            int n = input.nextInt();
            ArrangeCoins a = new ArrangeCoins();
            System.out.println(a.arrangeCoins(n));
        }

    }
}
